// m

// 给定代表不同面额的硬币数组coins和一个总金额amount
// 要求：求出凑成总金额所需要的最少硬币个数，如果无法凑出，则返回-1

// 解题思路
// 思路1： 广度优先搜索
// 从amount开始，每次从coins的硬币中选中一枚硬币，并记录当前挑选的硬币的次数，则最快减到0的次数就是凑成总金额所需的最少的硬币个数
// 这道题就变成了从amount减到0的最短路径问题，我们可以用广度优先搜索的方法来做
// 1. 定义visited为标记已访问值的set集合变量，queue为存放值的队列
// 2. 将amount状态标记为访问，并将其加入到队列queue
// 3. 令当前步数加1，然后将当前队列中的所有值依次出队，并遍历硬币数组
//      1. 如果当前值等于当前硬币值，则说明当前硬币刚好能凑成当前值，则直接返回当前次数
//      2. 如果当前值大于当前硬币值，并且当前值减去当前硬币值的差值没有出现在已访问集合visited中，则将差值添加到队列和访问集合中
// 4. 重复执行第3步，直到队列为空
// 5. 如果队列为空，也未能减到0，则返回-1

function coinChange(coins, amount) {
    if (amount === 0) {
        return 0
    }
    let visited = new Set([amount])
    let queue = [amount]
    let step = 0
    while (queue.length) {
        step += 1
        let size = queue.length
        for (let i = 0; i < size; i++) {
            let cur = queue.shift()
            for (let j = 0; j < coins.length; j++) {
                if (cur === coins[j]) {
                    return step
                } else if (cur > coins[j] && !visited.has(cur - coins[j])) {
                    queue.push(cur - coins[j])
                    visited.add(cur - coins[j])
                }
            }
        }
    }
    return -1
}


// 思路2：完全背包问题
// 可以转换为有n枚不同的硬币，每种硬币可以无限次使用，凑成总金额为amount的背包，最少需要多少硬币
// 1. 划分阶段， 按照子串的起始位置进行阶段划分
// 2. 定义状态，定义状态dp[i]表示为：凑成总金额为i的最少硬币数量
// 3. 状态转移方程，dp[i]来源于两部分
//      - 不使用当前硬币，只使用之前硬币凑成金额i的最少硬币数量
//      - 凑成金额 i- num的最少硬币数量，再加上当前硬币
//  上述两者的较小者即为dp[i]
// 4. 初始条件，凑成总金额为0的最少硬币数量为0，即dp[0] = 0
// 5. 最终结果，根据之前定义的状态，dp[i]表示为：凑成总金额为i的最少硬币数量，则最终结果为dp[amount]

function coinChange1(coins, amount) {
    let dp = new Array(amount + 1).fill(Infinity)
    dp[0] = 0
    for (let c = 0; c < coins.length; c++) {
        for (let i= coins[c]; i < amount + 1; i++) {
            dp[i] = Math.min(dp[i], dp[i - coins[c]] + 1)
        }        
    }
    if (dp[amount] !== Infinity) {
        return dp[amount]
    } else {
        return -1
    }
}

let coins = [1, 2, 5], amount = 11

console.log(coinChange1(coins, amount))